/*尝试把一个正整数分拆成若干个平方数的和，输出可能的方案数
思路：从最接近输入整数的平方数开始尝试，例如：
    输入：18
    进循环：
        第一次循环18-16 = 2，2进递归
        第二次循环18-9 = 9， 9进递归
        ......
        最后一次循环18-4 =14 14进递归
        递归中传参小于4则视为递归基，方案加1退出
*/

#include <iostream>
#include <cmath>
using namespace std;

int methods_num = 0;
void try_func(int mi)
{
    if (mi < 4)
    {
        methods_num++;
        return;
    } // 递归基，如果得到的差是小于4的就只能用1来累和

    // 找距离mi最近的平方数
    for (int i = sqrt(mi); i > 1; i--) // 这里sqrt自动向下取整取到平方后最接近mi的i
    {
        int ni = mi - pow(i, 2);
        try_func(ni);
    }
    methods_num++;
    return;
}

int main()
{
    int n;
    cin >> n;
    try_func(n);
    cout << methods_num;
    return 0;
}